10003 - Cutting sticks/10003.cpp

   1 #include <iostream>
   2 #include <map>
   3 #include <algorithm>
   4 #include <climits>
   5 #include <vector>
   6
   7 using namespace std;
   8
   9 typedef pair<int,int> point;
  10
  11 vector<int> p;
  12 map<point, int> cache;
  13
  14 int f(point n){
  15   //  cout << "n: " << n.first << " " << n.second << endl;
  16   if (cache.count(n) > 0){
  17     //cout << "Retornando " << cache[n] << endl;
  18     return cache[n];
  19   }
  20   //first < second
  21   if (n.second < n.first) swap(n.first, n.second);
  22
  23   for (int k=0; k<p.size()-1; ++k){
  24     if (p[k]<=n.first && n.first<=p[k+1] &&
  25         p[k]<=n.second && n.second<=p[k+1]){
  26       cache[n] = 0;
  27       //cout << "Retornando 0" << endl;
  28       return 0;
  29     }
  30   }
  31
  32   int min=INT_MAX;
  33   for (int k=0; k<p.size(); ++k){
  34     if (n.first<p[k] && p[k]<n.second){
  35       int q = n.second - n.first + f(point(n.first, p[k])) + f(point(p[k], n.second));
  36       //cout << "q es: " << q << endl;
  37       if (q < min){
  38         min = q;
  39       }
  40     }
  41   }
  42   //cout << "min es: " << min << endl;
  43   cache[n] = min;
  44   //cout << "Retornando " << min << endl;
  45   return min;
  46
  47 }
  48
  49 int main(){
  50   int l;
  51   while (cin >> l && l > 0){
  52     int n;
  53     cin >> n;
  54     cache.clear();
  55     p = vector<int>(n+2);
  56     p[0] = 0;
  57     p[n+1] = l;
  58     for (int i=1; i<=n; ++i){
  59       cin >> p[i];
  60     }
  61     cout << "The minimum cutting is " << f(point(0, l)) << ".\n";
  62   }
  63   return 0;
  64 }